package com.javabasic.algorithm.sword_of_offer;

/**
 * @author mir.xiong
 * @version 1.0
 * @description
 * @see
 * @since Created by work on 2022/6/26 13:22
 */
public class 粉刷房子 {

    private final int COL_NUM = 3;
    private int[][] dp;

    /**
     * 反向动态规划
     *
     * @param costs
     * @return
     */
    public int minCost(int[][] costs) {
        int len = costs.length;

        dp = new int[len][COL_NUM];

        dp[len - 1][0] = costs[len - 1][0];
        dp[len - 1][1] = costs[len - 1][1];
        dp[len - 1][2] = costs[len - 1][2];

        /**
         * 从下往上走
         */
        for (int i = len - 2; i >= 0; i--) {
            for (int j = 0; j < COL_NUM; j++) {
                dp[i][j] = Math.min(dp[i + 1][(j + 1) % COL_NUM], dp[i + 1][(j + 2) % COL_NUM]) + costs[i][j];
            }
        }

        return Math.min(Math.min(dp[0][0], dp[0][1]), dp[0][2]);
    }
}
